t = int(input())
for i in range(t):
n , k = map(int , input().split())
s = input()
dic ={}
for j in range(len(s)):
if s[j] in dic:
dic[s[j]] += 1
else:
dic[s[j]] = 1
pairs = 0
singles= 0
for i in dic.values():
pairs += i//2
singles += i%2
ll = pairs//k
singles+= (pairs%k)*2
ll = ll*2
if singles>=k:
ll+=1
print(ll)// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define init ios::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define lowbits(x) (x&(-x))
#define INF 0x3f3f3f3f
#define uu __int128
#define PI acos(-1)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PII;
const int N=2e5+10, M=2*N;
const int mod=998244353;
const double eps=1e-6;
int n,k;
string s;
int cnt[26];
int dist[N];
void solve(){
cin >> n >> k;
cin >> s;
memset(cnt, 0, sizeof cnt);
for(int i=0; i<n; ++i){
cnt[s[i]-'a']++;
}
int ji=0,d=0;
for(int i=0; i<26; ++i){
if(cnt[i] & 1)++ji;
d += cnt[i]/2;
}
int ans=d/k * 2;
ji += d%k * 2;
if(ji >= k){
++ans;
}
cout << ans << endl;
}
int main()
{
init;
int t=1;
cin >> t;
while(t--)solve();
return 0;
}
1529A - Eshag Loves Big Arrays | 19. Remove Nth Node From End of List |
925. Long Pressed Name | 1051. Height Checker |
695. Max Area of Island | 402. Remove K Digits |
97. Interleaving String | 543. Diameter of Binary Tree |
124. Binary Tree Maximum Path Sum | 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts |
501A - Contest | 160A- Twins |
752. Open the Lock | 1535A - Fair Playoff |
1538F - Interesting Function | 1920. Build Array from Permutation |
494. Target Sum | 797. All Paths From Source to Target |
1547B - Alphabetical Strings | 1550A - Find The Array |
118B - Present from Lena | 27A - Next Test |
785. Is Graph Bipartite | 90. Subsets II |
1560A - Dislike of Threes | 36. Valid Sudoku |
557. Reverse Words in a String III | 566. Reshape the Matrix |
167. Two Sum II - Input array is sorted | 387. First Unique Character in a String |